// *****************************************************************************
// HelloWorld.cpp
//
// The following tasks are performed by this program
//  1. Derive an oaTech observer to handle conflicts in the technology hierarchy
//  2. Derive an oaLibDefsList observer to handle warnings related to lib.defs
//  3. Open the design
//  4. Print the library name
//  5. Print the cell name
//  6. Print the view name
//  7. Create nets with the names "Hello" and "World"
//  8. Save these nets
//  9. Run the net iterator and print the existing nets in the design
//
// ****************************************************************************
// Except as specified in the OpenAccess terms of use of Cadence or Silicon
// Integration Initiative, this material may not be copied, modified,
// re-published, uploaded, executed, or distributed in any way, in any medium,
// in whole or in part, without prior written permission from Cadence.
//
//                Copyright 2002-2005 Cadence Design Systems, Inc.
//                           All Rights Reserved.
//
// To distribute any derivative work based upon this file you must first contact
// Si2 @ contracts@si2.org.
//
// *****************************************************************************
// *****************************************************************************

#include <iostream>
#include "oaDesignDB.h"

#include "/w/class/ee201a/ee201ata/oa/examples/oa/common/commonTechObserver.h"
#include "/w/class/ee201a/ee201ata/oa/examples/oa/common/commonLibDefListObserver.h"
#include "/w/class/ee201a/ee201ata/oa/examples/oa/common/commonFunctions.h"
#include <ctime>

#include <stdio.h>
#include <iomanip>
#include <sys/time.h>
#include <unistd.h>
#include "./Project.h"

using namespace oa;
using namespace std;

static oaNativeNS ns;

void cal_time (struct timeval start,int i) {
		struct timeval end;
		gettimeofday(&end,NULL);
		unsigned long diff = 1000000*(end.tv_sec-start.tv_sec)+ (end.tv_usec-start.tv_usec);
        cout<<"*** Time of step "<<i<<" = "<<(double)diff/1000000<<" seconds"<<endl;
}


int compareRow(const void * rr1, const void * rr2){
	MyRow r1 = *(MyRow*) rr1;
	MyRow r2 = *(MyRow*) rr2;
	return r1.y - r2.y;
}

int compareInst(const void * ir1, const void * ir2){
    MyInst i1 = *(MyInst*) ir1;
    MyInst i2 = *(MyInst*) ir2;
    if( i1.row == i2.row){
        return i1.x - i2.x;
    }
    else{
        return  i1.row -  i2.row;
    }
}

int compareInstX(const void* ir1, const void* ir2){ //add by Qirong
        return (**(MyInst**) ir1).x - (**(MyInst**) ir2 ).x;
}

int compareRow_surplus(const void * ir1, const void * ir2){
    MyRow i1 = *(MyRow*) ir1;
    MyRow i2 = *(MyRow*) ir2;
    if( i1.surplusonRow == i2.surplusonRow){
        return i1.y - i2.y;
    }
    else{
        return  i2.surplusonRow -  i1.surplusonRow;
    }
}

int compareInst_surplus(const void * ir1, const void * ir2){
    MyInst i1 = *(MyInst*) ir1;
    MyInst i2 = *(MyInst*) ir2;
    if( i1.surplus == i2.surplus){
		if(i1.y==i2.y){return i1.x - i2.x;}
			else{return i1.y-i2.y;}
    }
    else{
        return  i2.surplus - i1.surplus;
    }
}

// ****************************************************************************
// printDesignNames()
//
// This function gets the library, cell and view names associated with the open
// design and prints them.
// ****************************************************************************
void
printDesignNames(oaDesign *design)
{
    oaString    libName;
    oaString    cellName;
    oaString    viewName;

    // Library, cell and view names are obtained.
    design->getLibName(ns, libName);
    design->getCellName(ns, cellName);
    design->getViewName(ns, viewName);

    // Library, cell and view names are printed.
    //cout << "\tThe library name for this design is : " << libName << endl;
    //cout << "\tThe cell name for this design is : " << cellName << endl;
    //cout << "\tThe view name for this design is : " << viewName << endl;
}

// ****************************************************************************
// rmOverlap()
//
// remove overlap on each row
//	by Qirong Wang
// ****************************************************************************
void rmOverlap(MyInst * Insts, MyRow * myrow, int numRows, int leftbound, int rightbound, int numInsts)
{
	int rowWidth = (rightbound-leftbound);
	int m,n,k,j,i,p;
	int iRow;
	int costLeft, costUp, edgeWeight, numSites, step; 
	int *x, *w;
	int move=0, width=0, numInstonRow=0;
	InstsVec InstsTemp;
	MyInst** InstsonRow;
	
		//**legalize each row
	for(iRow = 0; iRow<numRows; iRow++){
	
			//**get cells on row 
		for(int t=0 ; t < numInsts ; t++)
			if(Insts[t].y == myrow[iRow].y)
				InstsTemp.push_back(&Insts[t]);				
		numInstonRow = InstsTemp.size();
		m = numInstonRow +1 ; 				//length of x[] and w[] m = total cell number+1		
		InstsonRow = new MyInst*[numInstonRow];
		for(int t=0; t<numInstonRow; t++)
			InstsonRow[t] = InstsTemp[t];			
		qsort(InstsonRow, numInstonRow , sizeof(MyInst*), compareInstX); //add by Qirong
				
			x = new int[m];   							//left position of each cell
			w = new int[m];  							//width of each cell
			numSites=myrow[iRow].numSites;				//number of sites on each row
			step = rowWidth / numSites;					//step is the unit to move cell
			
					//**get cell width w[i] and cell position x[i]
			for(j=1 ; j<m; j++){
				x[j] = (InstsonRow[j-1]->x1 -leftbound)/step; //all x[j] relative position to left bound
				w[j] = (InstsonRow[j-1]->x2 - InstsonRow[j-1]->x1)/step;	
			}
			n = rowWidth/step +1; 
		
					//**allocate space for cost[][]			
			int** costV = new int*[m];
			for(i=0;i<m; i++)
				costV[i] = new int[n];
						
					//**initialize cost function	
			for(j=1 ; j<m; j++) costV[j][0] = INFINITE;				
			for(k=1; k<n; k++) costV[0][k] = 0;	
		
					//**get cost value of each vertex
			for(j=1; j<m; j++){
				for(k=1; k<n ;k++){	
					costLeft = costV[j][k-1];
					costV[j][k] = costLeft;
					if( k>w[j]){
						edgeWeight =  abs(k-w[j]-x[j]); // > 0)?(k-w[j]-x[j]):(-(k-w[j]-x[j]));
						costUp = costV[j-1][k-w[j]] + edgeWeight;
						if(costUp < costLeft) 
							costV[j][k] = costUp;
					}
				}			
			}	
		
				//**get optimal overlap solution
			j=m-1;
			k=n-1;
			costLeft = costV[j][k-1];
			costUp = costV[j-1][k-w[j]] + abs(k-w[j]-x[j]);
		
			for(j=m-1; j>0; j--){	
				while(costLeft<costUp && k>w[j]){
					k--;
					costLeft = costV[j][k-1];		
					edgeWeight =  abs(k-w[j]-x[j]);
					costUp = costV[j-1][k-w[j]]+edgeWeight;
				}

					//**move cell virtually
				k = k-w[j];
				InstsonRow[j-1]->SetLowerLeftCoord( k*step+leftbound, InstsonRow[j-1]->y1);				
			}
				
				//**clear memory
			for(i = 0; i < m; i++) 
				delete []costV[i]; 
			delete []costV;
			delete []x;
			delete []w;
			
		InstsTemp.clear();
		delete []InstsonRow;
	}		
}


// ****************************************************************************
// main()
//
// This is the top level function that opens the design, prints library, cell,
// and view names, creates nets, and iterates the design to print the net 
// names.
// ****************************************************************************

int
main(int    argc,
     char   **argv)
{
    if( argc< 3){
	cout<< "oaDatabase should be in current directory"<<endl;
    	cout << "syntax: " << endl;
    	cout << "./VioChecker" << " [oaLib] [top_Cell]" << endl;
	exit(1);
	}

    try {
        // Initialize OA with data model 3, since incremental technology
        // databases are supported by this application.
        oaDesignInit(oacAPIMajorRevNumber, oacAPIMinorRevNumber, 3);
		oaString                librarypath="./";
		librarypath += argv[1];
        oaString                libPath(librarypath);
        oaString                library(argv[1]);
		oaViewType      	*viewType = oaViewType::get(oacMaskLayout);
        oaString        	cell(argv[2]);
       	oaString        	view("layout"); 
		oaScalarName            libName(ns,  library);
		oaScalarName            cellName(ns,  cell);
		oaScalarName            viewName(ns,  view);
		oaScalarName    	libraryName(ns,library);
        // Setup an instance of the oaTech conflict observer.
        opnTechConflictObserver myTechConflictObserver(1);

        // Setup an instance of the oaLibDefList observer.
        opnLibDefListObserver   myLibDefListObserver(1);

        // Read in the lib.defs file.
		oaLib *lib = oaLib::find(libraryName);

        if (!lib) {
            if (oaLib::exists(libPath)) {
                // Library does exist at this path but was not in lib.defs
                lib = oaLib::open(libraryName, libPath);
            } else {
		cout<<"Library not found!"<<endl;
		exit(1);
            }
            if (lib) {
                // We need to update the user's lib.def file since we 
                // found the library without a lib.defs reference.
                updateLibDefsFile(libraryName, libPath);
            } else {
                // Print error mesage 
                cerr << "ERROR : Unable to create " << libPath << "/";
                cerr << library << endl;
                return(1);
            }
        }
		// Create the design with the specified viewType,
        // Opening it for a 'write' operation.

        oaDesign    *design = oaDesign::open(libraryName, cellName, viewName,
                                             viewType, 'A');

        // The library, cell, and view names are printed.
        printDesignNames(design);

		// Get the TopBlock for this design.
        oaBlock *block = design->getTopBlock();
	
		// If no TopBlock exist yet then create one.
        if (!block) {
            cout<<"Top cell not found!"<<endl;
		exit(1);
        }
	
    	ofstream outerrorlist("VioList.error", ios::out);
		

		
		//------------------------------------START, find rows number and location. define rows -------------------------------------------------------------------------------------//
    	oaCollection<oaRow,oaBlock> CollectionRows = block->getRows();
    	int numRows = CollectionRows.getCount();
		// int* RowsY = (int*) malloc(sizeof(int)*numRows);
		MyRow* myrow = (MyRow*) malloc(sizeof(MyRow)*numRows);
		int i=-1;//Couter
    	oaIter<oaRow> rowIter(block->getRows());
    	//cout<<"numRows:"<<numRows<<endl;
		int leftbound,rightbound;
    	while( oaRow* RowP = rowIter.getNext() ){
			i++;
        	oaBox bbox;
        	oaPoint p;
	        RowP->getBBox(bbox);
        	bbox.getCenter(p);
	        myrow[i].y=p.y();			
			myrow[i].setRow(RowP);  //add by Qirong Wang initialize myrow 
					
				//********************************************************
				//-------If left/right bound are always the same, this can be removed----------

        	p=bbox.lowerLeft();
	        leftbound = p.x();
			
        	p=bbox.upperRight();
	        rightbound = p.x();
			
        	if(i>=numRows){
		    cout<<"error: num rows exceeding!"<<endl;
	            break;
        	}
		}
				
			//**Sort rows by their coordinate y
		qsort(myrow, numRows, sizeof(MyRow),compareRow);
		oaCollection<oaInst,oaBlock> CollectionInsts=block->getInsts();
		int numInsts = CollectionInsts.getCount();
		//cout<<"numInsts"<<numInsts<<endl;
		MyInst* Insts = (MyInst*) malloc(sizeof(MyInst)*numInsts);
		
		oaIter<oaInst> instIter(block->getInsts());
		i=0;//Counter
		int rowVioCount=0;
		int* numInstonRow = (int*)malloc(sizeof(int)*numRows);
		for(int j=0;j<numRows;j++){
			numInstonRow[j]=0;
		}
		
		while(  oaInst* InstP = instIter.getNext()){
			if(i>=numInsts){
					 cout<<"error: num rows exceeding!"<<endl;
					 break;
			}
			Insts[i].setInst(InstP);
				//**Locate the row number using binary search
			int low=0, current=numRows/2, high=numRows-1;
			while(low<=high){
				if(Insts[i].y == myrow[current].y){
					if(Insts[i].x1<leftbound){
						Insts[i].SetLowerLeftCoord(Insts[i].x1+(leftbound-Insts[i].x1),Insts[i].y1);
						Insts[i].row=current;
						numInstonRow[current]++;
						break;
					}
					if(Insts[i].x2>rightbound){
						Insts[i].SetLowerLeftCoord(Insts[i].x1+(rightbound-Insts[i].x2),Insts[i].y1);
						Insts[i].row=current;
						numInstonRow[current]++;
						break;
					}
					else{
					Insts[i].row=current;
					numInstonRow[current]++;
					}
					break;
				}
				else{
					if(Insts[i].y < myrow[current].y){
						high = current-1;
						current=(low + high)/2;
					}
					else{
						low = current+1;
						current = (low + high)/2;
					}
				}
			}
			
			if(Insts[i].x1<leftbound)
			Insts[i].SetLowerLeftCoord(Insts[i].x1+(leftbound-Insts[i].x1),Insts[i].y1);
			
			if(Insts[i].x2>rightbound)
			Insts[i].SetLowerLeftCoord(Insts[i].x1+(rightbound-Insts[i].x2),Insts[i].y1);
			
			if(low>high){
			
				if(abs(Insts[i].y-myrow[low].y)<abs(Insts[i].y-myrow[high].y)){
					Insts[i].SetLowerLeftCoord(Insts[i].x1,Insts[i].y1-Insts[i].y+myrow[low].y);
					Insts[i].row=low;
					numInstonRow[low]++;
				}
				else{
					Insts[i].SetLowerLeftCoord(Insts[i].x1,Insts[i].y1-Insts[i].y+myrow[high].y);
					Insts[i].row=high;
					numInstonRow[high]++;
				}			
			}
			i++;
		}
		
//	--------------------------------------------------------------------------------------------------------------------------------------
//  -----------------------Calculate cell width and row cell width total and Row surplus------------------------------------------
		qsort(myrow, numRows, sizeof(MyRow),compareRow);
			//***time consuming******//			
		//qsort(Insts, numInsts, sizeof(MyInst),compareInst);
		
		int rowcellwidth;
		int cellwidth;
		int iInst1=0;
		
		//*add by qirong, improve runtime
		vector<InstsVec> allInsts;
		int num;
		for(int k=0; k<numRows; k++){
			InstsVec InstsRow;
			allInsts.push_back(InstsRow);
			rowcellwidth=0;
			num =0;
			for(int j=0; j<numInsts; j++){
				if(Insts[j].y == myrow[k].y){
					allInsts[k].push_back(&Insts[j]);
					num++;
					cellwidth=Insts[j].x2 - Insts[j].x1; //Insts[iInst1].x2-Insts[iInst1].x1;
					rowcellwidth+=cellwidth;
				}
			}			
			myrow[k].surplusonRow= rowcellwidth-(rightbound-leftbound);
			myrow[k].numInstonRow=num;
			myrow[k].rowcellwidth=rowcellwidth;
		}
			
			//------------------------------------Order row as descending surplus-----------------------------------------------------------------------------
		qsort(myrow, numRows, sizeof(MyRow), compareRow_surplus);				
		for(int p=0; p<numRows; p++) {			
			while(myrow[p].surplusonRow>0){
			
				int DeltaBest=9999999999;
				int DeltaHPWL=-1;
				int RowBest=-1;
				int CellBest=-1;
				int formerRow=-1;
				
				InstsVec InstsonRow;
				for(int i=0 ; i < numInsts ; i++)
					if(Insts[i].y == myrow[p].y)
						InstsonRow.push_back(&Insts[i]);
						
				//qsort(&InstsonRow, InstsonRow.size(), sizeof(MyInst), compareInstX); //add by Qirong
				
				//========determine which cell to move to which row====================
				
				for(int j=0; j<InstsonRow.size(); j++){
					for(int k=0; k<numRows; k++){					
						if((myrow[k].surplusonRow<0)&&(-(myrow[k].surplusonRow)>(InstsonRow.at(j)->x2-InstsonRow.at(j)->x1))){
							DeltaHPWL=abs(myrow[k].y-InstsonRow.at(j)->y);
							if(DeltaHPWL<DeltaBest){
								DeltaBest=DeltaHPWL;
								RowBest=k;
								CellBest=j;
								formerRow=p;
							}								
						}			
					}
				}
				
				if(CellBest==-1)
					break;				
				else{
					//==================Move the best cell to the best row=============================
					InstsonRow.at(CellBest)->SetCenterCoord(InstsonRow.at(CellBest)->x, myrow[RowBest].y);
					myrow[RowBest].numInstonRow++;
					myrow[formerRow].numInstonRow--;
					//================update surplus of start and destination row========================
					myrow[formerRow].surplusonRow -= (InstsonRow.at(CellBest)->x2 - InstsonRow.at(CellBest)->x1);
					myrow[RowBest].surplusonRow += (InstsonRow.at(CellBest)->x2 - InstsonRow.at(CellBest)->x1);
				}			
			}
		}			

//------------------------------------Remove Overlap ---------------------------------------------------
		qsort(myrow, numRows, sizeof(MyRow),compareRow);
		
		rmOverlap(Insts, myrow, numRows, leftbound, rightbound, numInsts);	

				//**move instances to position in layout
		for(int i=0; i<numInsts; i++)
			Insts[i].Instpointer->setOrigin( oaPoint(Insts[i].Originx,Insts[i].Originy) );
	
		//The design is saved.
		design->save();
		
		// The design is closed.   
		design->close();

		// The library is closed.   
		lib->close();
	
	}catch (oaCompatibilityError &ex) {
        handleFBCError(ex);
        exit(1);

    } 
	
	catch (oaException &excp) {
        cout << "ERROR: " << excp.getMsg() << endl;
        exit(1);
    }

    return 0;
}
